/*
 * @lc app=leetcode.cn id=98 lang=typescript
 *
 * [98] 验证二叉搜索树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

//  思路：迭代
//  利用左子树都比右子树小的特性进行递归，但最终无法与root进行合并，因此通过辅助函数增加参数携带信息进行判断
//  参考：https://labuladong.github.io/algo/2/19/26/

//  复杂度：O(n) O(n)

function isValidBST(root: TreeNode | null): boolean {
    return isValid(root, null, null)
};

function isValid(root: TreeNode | null, min: TreeNode | null, max: TreeNode | null): boolean {
    if (!root) return true
    // 若 root.val 不符合 max 和 min 的限制，说明不是合法 BST
    if (max && root.val >= max.val) return false
    if (min && root.val <= min.val) return false
    // 限定左子树的最大值是 root.val，右子树的最小值是 root.val
    return isValid(root.left, min, root) && isValid(root.right, root, max)
}
// @lc code=end

import { TreeNode } from "./type"
const root = TreeNode.buildTree([5, 1, 4, null, null, 3, 6])
const root2 = TreeNode.buildTree([2, 1, 3])
console.log(isValidBST(root))
console.log(isValidBST(root2))
